import sys

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        last = -sys.maxsize
        bound = -1
        for i in range(len(nums)-1, -1, -1):
            if nums[i]>=last:
                last = nums[i]
                bound = i
            else:
                break
        if bound != 0:
            suffix = list(nums[bound:])
            bound-=1
            suffix.sort()
            for i in range(len(suffix)):
                if suffix[i]>nums[bound]:
                    suffix[i], nums[bound] = nums[bound], suffix[i]
                    break
            for i in range(bound+1, len(nums)):
                nums[i]=suffix[i-bound-1]
        else:
            nums.sort()
nums = [1,1,5]
Solution().nextPermutation(nums)
print(nums)